#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""


class Solution:
    def minimumTotal(self, triangle):
        # write your code here
        rows = cols = len(triangle)
        mat = self.make_matrix(rows, cols, 0)

        mat[rows-1] = triangle[rows-1]

        # print(mat)
        for row in range(rows-2, -1, -1):
            # 0 ------> row-2
            for col in range(0, row+1):
                cur = triangle[row][col]
                mat[row][col] = min(mat[row+1][col], mat[row+1][col+1]) + cur

        return mat[0][0]

    def make_matrix(self, rows, cols, init_v=None):
        one_row = [init_v] * cols

        mat = [list(one_row) for i in range(rows)]
        return mat








def main():
    # path = [
    #          [2],
    #         [3,4],
    #        [6,5,7],
    #       [4,1,8,3]
    # ]

    print("start main")
    s = Solution()
    path = [
        [2],
        [3,4],
        [6,5,7],
        [4,1,8,3]
    ]
    ret = s.minimumTotal(path)
    print(ret)

if __name__ == "__main__":
    main()
